package algorithm.poj.p2000;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.net.URL;
import java.net.URLDecoder;


/**
 * 分析：
 * 经典问题，根据二叉树的前序遍历和中序遍历，计算后序遍历。
 * 
 * 实现：
 * 
 * 经验和教训：
 * 
 * 
 * @author wong.tong@gmail.com
 *
 */
public class P2255 {

	public static void main(String[] args) throws Exception {

		InputStream input = null;
		if (false) {
			input = System.in;
		} else {
			URL url = P2255.class.getResource("P2255.txt");
			File file = new File(URLDecoder.decode(url.getPath(), "UTF-8"));
			input = new FileInputStream(file);
		}
		
		BufferedReader stdin = new BufferedReader(new InputStreamReader(input));

		String line = stdin.readLine();
		while (line != null) {
			String[] tmp = line.trim().split(" ");
			char[] postord = recover(tmp[0].toCharArray(), tmp[1].toCharArray());
			System.out.println(new String(postord));
			line = stdin.readLine();
		}
	}

	/**
	 * 递归
	 * @param preord
	 * @param inord
	 * @return
	 */
	private static char[] recover(char[] preord, char[] inord) {
		
		if (preord.length == 0) {
			return new char[0];
		} else if (preord.length== 1) {
			return new char[] {preord[0]};
		} else {
			char m = preord[0];
			int index = 0;
			for (;index < inord.length; index ++) {
				if (inord[index] == m) {
					break;
				}
			}
			
			//iterate
			int len1 = index;
			char[] npre1 = new char[len1];
			for (int i = 0; i < len1; i ++) { npre1[i] = preord[i+1]; }
			char[] nin1 = new char[len1];
			for (int i = 0; i < len1; i ++) { nin1[i] = inord[i]; }
			char[] npost1 = recover(npre1, nin1);
			
			int len2 = preord.length-index-1;
			char[] npre2 = new char[len2];
			for (int i = 0; i < len2; i ++) { npre2[i] = preord[index+i+1]; }
			char[] nin2 = new char[len2];
			for (int i = 0; i < len2; i ++) { nin2[i] = inord[index+i+1]; }
			char[] npost2 = recover(npre2, nin2);
			
			//return
			char[] postord = new char[preord.length];
			for (int i = 0; i < len1; i ++) { postord[i] = npost1[i]; }
			for (int i = 0; i < len2; i ++) { postord[len1+i] = npost2[i]; }
			postord[postord.length-1] = m;
			return postord;
		}
	}
}